/*
 * Copyright (c) 2021
 * User:Administrator
 * File:N叉树的后续遍历.java
 * Date:2021/02/21 17:01:21
 */

package com.mlamp.二叉树;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个N叉树，返回其节点的后续遍历
 */
public class N叉树的先续遍历 {


    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node3 = new TreeNode(3);
        root.childs = new TreeNode[]{
                node3,
                new TreeNode(2),
                new TreeNode(4)
        };
        node3.childs = new TreeNode[]{
                new TreeNode(5),
                new TreeNode(6)
        };

        N叉树的先续遍历 instance = new N叉树的先续遍历();
        instance.preOrderTraversal(root);
        System.out.println();

        instance.preOrderTraversal2(root);

        instance.postOrderTraversal3(root);


    }


    /**
     * 数据结构设计
     */
    private static class TreeNode {
        int value;
        TreeNode[] childs;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    /**
     * 递归算法
     *
     * @param root
     */
    public void preOrderTraversal(TreeNode root) {
        if (root == null) return;
        //一定要判断 root.childs 是否为null
        System.out.print(root.value + " ");
        for (int i = 0; root.childs != null && i < root.childs.length; i++) {
            preOrderTraversal(root.childs[i]);
        }
    }

    /**
     * 非递归算法
     */

    public void preOrderTraversal2(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) return;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            sb.append(node.value).append(" ");
            if (node.childs != null) {
                for (int i = node.childs.length - 1; i >= 0; i--) {
                    stack.push(node.childs[i]);
                }
            }
        }
        System.out.println(sb.toString());
    }


    /**
     * 非递归算法2
     */

    public void postOrderTraversal3(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) return;
        Deque<TreeNode> stack = new ArrayDeque<>();
        Deque<TreeNode> stack2 = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            stack2.offer(node);
            if (node.childs != null) {
                for (int i = node.childs.length - 1; i >= 0; i--) {
                    stack.push(node.childs[i]);
                }
            }
        }
        while (!stack2.isEmpty()) {
            sb.append(stack2.poll().value).append(" ");
        }
        System.out.println(sb.toString());
    }


}
